#include<iostream>
#include<queue>
#include<string>
#include<sstream>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Codec {
public:
	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		if (!root) return "";
		queue<TreeNode*> nodes;
		string res = "";
		nodes.push(root);
		TreeNode *t;
		while (!nodes.empty()) { 
			t = nodes.front();
			if (!t) {
				res += "N ";
				nodes.pop();
				continue;
			}
			res =res+ to_string(t->val) + " ";
			nodes.push(t->left);
			nodes.push(t->right);
			nodes.pop();
		}
		return res;
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		if (data == "") return NULL;
		istringstream buf(data);
		vector<string> list;
		string val,temp;
		while (buf >> val) {
			list.push_back(val);
		}
		queue<TreeNode *> q;
		TreeNode *root= new TreeNode(stoi(list[0]));
		q.push(root);		
		int left = 1, right = 2;
		while (right <= list.size() - 1){
			TreeNode *parent = q.front();
			if (list[left] != "N") {
				TreeNode *l=new TreeNode(stoi(list[left]));
				parent->left = l;
				q.push(l);
			}
			if (list[right] != "N") {
				TreeNode *r=new TreeNode(stoi(list[right]));
				parent->right = r;
				q.push(r);
			}
			left += 2,right+=2;
			q.pop();
		}
   		return root;		
	}
};

void main() {
	TreeNode root(1), n2(2), n3(3), n4(4), n5(5);
	root.left = &n2, root.right = &n3, n3.right = &n5;
	Codec ser, deser;
	TreeNode* ans = deser.deserialize(ser.serialize(NULL));
}